package src.leetcode.hot.hard_0042;

public class trap {
    public static void main(String[] args) {
        int []height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(new Solution().trap(height));
    }
}

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int []lmaxh = new int[n];
        lmaxh[0] = 0;
        int []rmaxh = new int[n];
        rmaxh[n - 1] = 0;
        for(int i = 1; i < n; i++) {
            lmaxh[i] = Math.max(lmaxh[i - 1], height[i - 1]);
        }
        for(int i = n - 2; i >= 0; i--) {
            rmaxh[i] = Math.max(rmaxh[i + 1], height[i + 1]);
        }

        for(int i = 0; i < n; i++){
            System.out.print(lmaxh[i] + " ");
        }
        System.out.println();
        for(int i = 0; i < n; i++){
            System.out.print(rmaxh[i] + " ");
        }
        System.out.println();
        for(int i = 0; i < n; i++){
            System.out.print(height[i] + " ");
        }
        System.out.println();

        int ans = 0;
        for(int i = 1; i < n - 1; i++) {
            int up = Math.min(lmaxh[i], rmaxh[i]) - height[i];
            ans += Math.max(up, 0);
        }

        return ans;
    }
}
